{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unsupervised learning means a lack of labels: we are looking for structure in the data, without having an *a priori* intuition what that structure might be. A great example is clustering, where the goal is to identify instances that clump together in some high-dimensional space. Unsupervised learning in general is a harder problem. Deep learning revolutionized supervised learning and it had made significant advances in unsupervised learning, but there remains plenty of room for improvement. In this notebook, we look at how we can map an unsupervised learning problem to graph optimization, which in turn we can solve on a quantum computer.\n",
    "\n",
    "# Mapping clustering to discrete optimization\n",
    "\n",
    "Assume that we have some points $\\{x_i\\}_{i=1}^N$ lying in some high-dimensional space $\\mathbb{R}^d$. How do we tell which ones are close to one another and which ones are distant? To get some intuition, let's generate a simple dataset with two distinct classes. The first five instances will belong to class 1, and the second five to class 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:21.386145Z",
     "start_time": "2018-11-19T20:10:20.886249Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAGptJREFUeJzt3XtwVPXZB/DvOZvNnZAEkhgil2AIl3AxF3hfZ/R1ak061Bnt+E5H7bT6R2e0nfEyFVsqUhWkgaKgtDJqfRl5KVpaq4NWxiqjRrBCEgMISiVFgkFCBALZTUiyl3N+7x95d92EbDabbM45v3O+nxlHNCQ8QPabJ8/vchQhBIiIyBiq2QUQETkJQ5eIyEAMXSIiAzF0iYgMxNAlIjJQUoy3c2sDEVH8lGhvYKdLRGQghi4RkYEYukREBmLoEhEZiKFLRGQghi4RkYEYukREBmLoEhEZiKFLRGQghi4RkYEYukREBmLoEhEZiKFLRGSgWLeMEUUlhICu6/D5fAgGg0hKSoKqqnC5XFBVFaqqQlGiXrZE5EhKjAdT8mpHuowQApqmIRgMDvhx6G2RQRsK4dA/DGNyiKif4AxdGrHBYasoChRFQTAYRDAYhKqql/38yH8YxuQgUT+ROV6gmIQQCAaD0DQtHJ6DA3YooVAe6uMBQDAYRCAQGPA2hjHZHUOXogqFbWh0MNKwjSUUoIODdHAYR3bHiqLA5XKF58ahcGYYk2wYunQZXdcHzGmjdawhiQq+WGE8eLQhhBi2M2YgkxUxdClM1/XwGAGIHbZGGWkYD34fVVWRlJTEMCZLYeg6XGiRKxAIQNd1ANYJ21hihXFoO9vg9wl1x5GjCll+zyQ/hq5DhfbYBoNB6cI2lmhhDHz7+9Y0DX6/f8DbIscUoe7YLn8mZB0MXYcZHLahUHFKsAy3oyIUxoO3tw01M+aOChothq5DRNtjy+DoN5ow5vY2Gg0ejrC5aGGbSJqmIRAIJGQ7mSx48INi4OEIpxntgQYaGR78oNFi6NrMeB1oGA5D41sjPfgRKRS+PPjhDAxdm4j3QAMZiwc/KIShKzmrHmigkeHBD+dh6EpI5gMNNDI8+GFfDF2J2PlAA40MD37Ij6ErAacfaKCRiWevcejfPPhhPIauhfFAAyUCD35YCw9HWJARBxoSSdd1BAIBS9dII8eDHwnBx/XIYKgDDTJ8MjN0nSGUFaEwjsQwvgxD18qGOtAg0yerruvw+/088eZQscI42vY2m+MxYCuy04EGWeumsRvLwY/IrW1O2VHB0DWB3Q40yFw7jR8e/BgaQ9cgPNBA1M/pBz840x1nTjjQIISA3++31e+JrCVyN8VgkQt4oaYmKyvLhCoHiPpi4MrHOAlt+/L7/fD7/QOuV2Q4EcUnstMdvEsitJDb29uLXbt2Yd26dWaXOyyOFxKMBxqIjDP4teXxeDBx4kQTK4qNoZsgQ4Utt1ARGcvj8SA7O9vsMobFVBij0OKYz+cLX07NEQKROTweD3JycswuY1jsdEfJjCc0ENHwZOh0GbpxstOBBiK78Xq9DF27sNuBBiI78nq9XEiTGQ80EMmFM11JOeFAA5EdcaYrmdC2L03T+IQGIglpmga32212GcNi6IIHGojsIMaVBpbh6NDlgQYi+wiFrtWbJUeGLvfYJp7VP9HJ/vr6+pCenm52GTE5KnRlf0IDEUXX2dlphdvFYnJEexd6hldfXx+CwSBv+yLL6wv24aH3H8KC/1mAJf+7BK8fe93skixPhp0LgM1DN3Tlm8/nY9iOM1kWMWTx249/i7eOv4VkVzL8mh8r96xEfVu92WVZmgw3jAE2DN3QHlufzwefzwdN0xi2JJ0PvvoAqUmpcKkuJLuSEdSD2Pf1PrPLsrTOzk52ukaKvDTc5/OF99kybI3DbjdxclJzENAD4f9WFAU5adY+aWU2jhcMEloc4xMazMMFycR77NrHkKQkocvXhS5/F2Zmz8Sts281uyxLk+GyG0Di3Qs80EB2VlVYhZ3/vRP72vYhIykDNxbfiAx3htllWZrH40FhYaHZZcQkXejyQAM5RXF2MYqzi80uQxocL4wTTdP4hAYiuowsoStdpxt63j0RUSRZQpfpRUS24PV6LX+XLsDQJSKbYKc7TjjDJaKhBAIBpKSkmF1GTNKFLlkTvxiSmWQ6mCNd6PLFTUTRyJAP0oUuIMcfLBEZp6+vT4rRAiBp6BIRRZLlhjGAoUtENiDLzgVA0tDleIGIInm9Xna6RERG6ezsZOiOJ3a6RBSJ4wVyHH4hJDPJ8tQIQNLQ5QuciCLJcu8CIGnoEhFF4niBHEmmo5hkL7I8qgeQNHQ5XiCKjy509AZ6zS5j3Mh0OEK6S8yJKD51rXVYu28t+gJ9mDNpDtZcvwZ56Xlml5VQHo+HM93xxE6XaGROek5i9UerkeJKQUFGAZovNOOxvY+N6WMKIfDx1x/jyfonsblpM77yfJWgakdPptBlp0tkY8cvHgcApCWlAQDy0vPw2bnPoOkaXKprVB9zz6k9ePHQi8hOzYZf8+PTs59i9XWrcUXmFQmrO14+nw9paWmm/frxkLLTJevhdx/WlJuaC13o0IUOALgUuISc1JxRBy4AvNvyLianT0ZOag4KMgrgC/pw8JuDiSo5brIt4ErZ6fIFThTby5+/jBcPvYhzPefQ5e9Cdko2VEXFqutWjenjuhTXgKATEHApow/xRJElF6QMXaD/D1i2r3BERtl2ZBt+9cGv0BPsAQCkuFJwz3/dg5tn3TzmMcAts27Bpk82oSfYg6AexMSUiagsrExE2aMSCATgdrtN+/XjJW3oElF0mw9sDgcuAPg0H5q+acLd5XeP+WNXFlZi+X8uR+OZRqS703HD9BswKW3SmD/uaHk8HmRlZZn268dL2tBlp0sU3VDf7icpiXu5l+WVoSyvLGEfbyxkOo0GcCGNyJYe+o+HwjsWACA9KR33lN9jYkXjR6aDEYDknS4RDe3W2bcizZ2Glw6/hFRXKn6x5BdYmL/Q7LLGhUw3jAEShy4RDW/pzKVYOnOp2WWMO5kORgAcL1CC8DsPMovX65VqIU3a0OWLnIgAdrpERIaSbaYrbeiy0yUiQK67dAGJQ5eICOA+XSIiQ3GmaxCOF4gIkOuhlIDEoUvWwy+EZIaenh5p7tIFJA5dvsCJKHT/iqrKE2XyVDoEBq+18AIiMotMWSB16JK1yPSJT/YQDAbhcpl/gXo8GLqUEAxcMoNsR4AByUOXL3QiZ5Ntjy4geegSkbPJdpcuIPnVjqZ0un4/1O3boXz2GURJCfS77gIyMoyvg4gYurYnBFyPPAK1rg5ISwM++ghqUxOCL7wAJPGPkshoHC8YzPBO99w5qHv3AgUFQHY2UFAA5ehRKP/+t7F1EBEAhq79hfahcgGPyBI6OzulOgIMMHTjk58P/ZprgPZ2wOMBzp6FKC2FmDXL7MqIHEm2ax0ByWe6ho8XFAXa2rUQ27ZBPXIE+lVXQf/pTznPJTKJ1+vlQprtpaZCv/tu6GbXQUSc6RqNhyOInE22u3QByUOXiJyNoUtEZKDu7m5kZmaaXUZcpJ7pWmq84PdDffVVKEePQhQXQ7/jDsedVNN1Xbobn0heMt6lC0geukB/8Jp+j6sQcNXWQt27FyI9Her+/VAOH4a2caMjdjYIIaDrOoQQCAQC4f+vqioURZHuRUFysVTzNQL2TwQjdHRA+ec/IaZMAVQVIicH6hdfQG9psfUe3lDY6nr/Xg632z0ggEM/1jQt/PNdLlf4RcIwprHQdV26wAVsELqW6HQl/Isfi8HBqijKgE/+yBFDKJBD4Rx6XwDhMA69P7tiikdXVxcmTJhgdhlxkz50LSE3F+Laa6F++CFERgaUnh7oZWUQxcXm1tXdDaWhAejoAKZOhaioAJKTR/3hQl/cNE0Lh22skAy9ffDPiwxgBjGNRmdnp3R7dAEbhK4lvr1QFGgPPwxRWgrl6FHoM2ZAv/12c+e5fj+UXbug9PYCmZnAp58C3d0QN944qg8XOUqIDMTRCgXp4K448tdhENNwZDwYAdggdC0jObl/x4JVXLwIxeMBior6/7uoCEpLC4TfH1e3O3huO9awHU6sII7siIPB4IDZMOfEziPjXboAQ9e+XC5A1/tvRlMUQNP6/z3CUDIybIcTLYiBb8ccg8cTQgioqhp1tEH2wE7XJJYYL1jRpEkQs2ZBaW7u72z9fohrr4058oi1SGYFQ4XpUAt2kbNngOMJu5HxshvABqFLUSgKxHe+A1FcDKW7GyI3F7jyyqg/fTSLZFbCBTvn6ezsRF5entllxE360LVaF2YpqgrMnIlYG+oSvUhmJVywsy+v14uSkhKzy4ib9KFLo2eVua3R4lmwCwVx6P24YGcdMl52AzB0HcmpYTscLtjJhwtpJnF6WMRDhkUyK4m1YDf4mDPHE8Zip0uWNng1n2EwOqNZsAt1xAzixOLuBZOwUxseRwnGGM2CXej9GMSj09XVxdA1iyUuvbEYhq35RrJgx5vYRk/W+5ttEbr0LYattXHBLjFkbrJsEbrsdLlIJrPh5sRcsBta6PUu4+e4LULX6bhIZk+R3W0IF+z6dXd3S3mXLsDQlRpHCc4z1oMddglij8eDrKwss8sYFVuErtOChmFLkZy4YCfrtY6ATULXKRi2NFLDLdjFenSSDAt2sj41ArBJ6EoVPB0dQF8fkJ8PuN0jehcuklEijGTBLrQ+AFh7wU7WI8CATUJXCkJAffllqG+80X/tYmEhtJUrgRhX03GRjCK1dbWhO9CNvPQ85KQm5gisjAt2DF2KSfn0U6ivvw4xdSrgckFpa4PrhRf6g3cIHCXQYO+eeBd1rXVQoUJVVPxkwU8wK3fWuPxaVl+wkzl0bdE2yRBGSnt7/+Ny/v+TWEyeDOXLLy/7eaHONhgMhu+3jbxSkJzpTPcZ1H1Vhyszr8TUrKnITs3GX47+xdD96aqqwuVywe12Izk5GampqUhOTobb7YbL5YKqquHP30AggEAgAL/fD03TBjQQieD1eqUNXXa6BhEFBf3PK9O0/uDt6ICYN+/bt7OzpWFcClyCqqhwqf1ftDPcGejo7YBf8yMlKcW0usayYDeW8YTMna4tQleGcBJXXw39llugvvVW/xMd8vMRvOceLpLRiExOm4wkNQnd/m5kJmfizKUzmJo11dTAjcaIRyex06XYFAX6nXdCX7q0f/fCFVdAuN1cJKMRyU7Nxl0L78KOozvQ6m3FtKxpuG3ebWaXFZdEPjpJ1rt0AUCJMROS5kIDn89ndgkjxlECjZYQAkE9CLdrZNsNZRStI45000034c0337TygymjvqDZ6RqIYUtjpSiKrQMXGH5O3NfXh40bN+LUqVNISbHeaGUkbPP9rJXDizsSiMZGVVUcPnwYS5cuRVpaGlpaWnj3Al0u8sw7F8mIRsfn82H9+vWoq6vDli1bsHDhQrNLGhN2uuMk1N2GFgTY2RLF7+DBg6iursaECROwZ88e6QMXYKebcJzbEo2dz+fDunXr8NFHH2Hr1q2YP3++2SUlDDvdBOHcligxmpqacOONNyInJwcffvihrQIXYKc7ZuxsiRKjr68Pa9euxb59+7Bt2zaUlZWZXdK4sE2na7TIS6HZ2RKNTWNjI6qrq5GXl4e6ujrbBi5go07XyLDjdYtEidHb24va2lo0NjZi+/btmDt3rtkljTumRRwi57bcAkY0NvX19aipqcGUKVPw/vvvOyJwAXa6I8K5LVHi9Pb2Ys2aNThw4ABeeeUVzJ492+ySDMVOdxjckUCUWPv27UN1dTWmTZuG999/33GBC7DTHRJPkhElVk9PD1avXo3Dhw9jx44dKC0tNbsk07DTHYQnyYgSRwiBjz/+GNXV1SgpKcF7773n6MAFbNTpjhXntkSJdenSJaxatQpHjx7Fq6++ipKSErNLsgTbdLqjDUjObYkSSwiBvXv3orq6GnPmzMHu3bsZuBFs1ekqijLiB/WxsyVKvO7ubjz22GNobm7Ga6+9hquuusrskizHNp3uSPEkGVHiCSGwZ88e1NTUYMGCBdi9ezcDNwpHdbpWOUmmnDgBpa0NorAQgp+YJLmuri48+uijOHHiBHbu3IkZM2aYXZKlOaLTtdJJMtcbbyD5Zz+D+4knkPzzn8P1t7+ZUgfRWAkhUFdXh5qaGpSXl+Odd95h4I6AbR5MCQCBQGDAQ+wsN7e9eBEpd9wBkZMDJCcDgQCUjg74Xn4ZmDzZvLqI4tTV1YWVK1eitbUVf/zjHzF9+nSzS7KaqEFjq043FKhW3ZGgeL39P0hO7v+32w0oChSPx7yiiOIghMAHH3yAmpoaLFmyBG+//TYDN062mulGdrZmjxGGIvLzIbKygAsXgNxcoLMTIjMTorDQ7NKIYvJ6vVi5ciVOnz6Nv//975g2bZrZJUnJVp3uihUrwg+w6+7uNrucy6WlIbB2LZCdDeX0aSAzE4HaWiA93ezKiKISQuC9995DTU0NrrnmGuzatYuBOwa2mukeO3YM+/fvR319PQ4cOAC/34/58+ejsrISixcvRllZGdxut9llAkIAPh+QkgJYqBMnGszj8WDFihU4e/Ysnn/+eUydOtXskmQR9YVtq9AdrK+vD4cOHcL+/fvR2NiIzz//HOnp6aisrERVVRWqqqowffp0XkJONIgQArt378ajjz6KBx98EHfeeSdfJ/FxZugOJoTAhQsX0NjYGA7ir776CldeeSUWL14cDuOcnBxLzYKJjNTZ2YmHH34YFy5cwPPPP4+ioiKzS5IRQzcaXddx8uRJ1NfXo76+Hp988gm6urowd+7ccAgvWrQIqampZpdKNK6EEHjnnXfw+OOP46GHHsKPf/xjdrejx9CNRyAQwJEjR8JBfPjwYSQlJaGiogIVFRWoqqrCrFmz4HK5zC6VKCEuXryIX//61/B6vXjuuecwZcoUs0uSHUN3LIQQ6OrqwieffIL6+no0NDTg+PHjyM/PHzAfLigo4FiCpCKEwNtvv41Vq1Zh+fLl+NGPfsTuNjEYuokmhEBbW1u4G25oaMD58+cxa9YsVFVVobKyEhUVFUhPT2cQkyVduHABy5cvR29vLzZv3oxC7hdPJIauETRNw7/+9S/U19ejsbERBw4cgKZpWLhwYbgbnjt3LpKSbHUmhSQjhMCuXbvwxBNPYMWKFbj99tvZGCQeQ9cMQgj09vaiqakJDQ0NqK+vxxdffIGJEyeG9w5XVVWhqKiI39KRITo6OvDLX/4SwWAQmzdvRkFBgdkl2RVD1yqEEDh//vyAscTp06cxY8aMcDdcUVGBiRMnsvughBFC4M0330RtbS0eeeQR3Hbbbfz8Gl8MXSvTdR3Hjx8Ph3BTUxN6enpQVlYWDuL58+cjJSXF7FJJQufPn8eyZcugKAqeffZZ5Ofnm12SEzB0ZeP3+3Ho0KFwEH/22WdITU1FeXl5OIhnzpzJsQRFJYTAzp07sW7dOvzmN7/BD3/4Q3a3xmHoyk4Igc7OTjQ2NoYX6k6cOIGioiJUVFSET9RNnjyZLyzC2bNnsWzZMrjdbvzhD39AXl6e2SU5DUPXjnRdx6lTp7B//340NDSgsbERnZ2dmD17dnihbtGiRUhLS2MQO4QQAq+//jrWr1+Pxx9/HLfeeiv/7s3B0HWKYDCIzz//PHy3xKFDh6AoCq6++urwQY7Zs2fzNJ0NffPNN1i2bBnS0tKwadMmTObTSMzE0HUqIQS6u7vR1NQUHks0Nzdj0qRJqKysRGVlJZYsWYIrrriCHZGkdF3Ha6+9hqeeegqrV6/GD37wA/5dmo+hS98SQqC9vR0NDQ3hjri9vR0lJSXhsUR5eTkyMzP54rW49vZ2PPjgg5gwYQKeeeYZTJo0yeySqB9Dl4anaRqam5vD8+GDBw/C7/djwYIF4SCeN2+eNS6BJ+i6jr/+9a94+umnsWbNGtx88838AmktDF2KX19fHw4ePDjgEvjMzMwBl/xMmzaN29YM1t7ejgceeAC5ubl4+umnkZuba3ZJdDmGLo2dEAIdHR0DLoFvbW3FtGnTwpf8VFZW8hL4caLrOnbs2IHf//73qK2txU033cQ/Z+ti6NL40HUdLS0tAy6B7+7uxrx588Id8cKFC3kJ/BidOXMGDzzwAPLy8rBx40bk5OSYXRINj6FLxvH7/QMugT9y5AjcbjfKy8vD8+GSkhKOJUZA13W88sorePbZZ7F27Vp8//vfZ3crB4YumUcIAa/XO+AS+C+//BIFBQUD5sP5+fkMlAhtbW24//77UVhYiA0bNiA7O9vskmjkGLpkLUIInD59GvX19eH5cEdHB0pLS8Pz4fLyckdeAq/rOrZv347nnnsOv/vd7/C9733PcX8GNsDQJevTNA1Hjx4Nd8MHDx6EEGLAJfBz5syx9SXwX3/9Ne6//35MnToVTz31FCZOnGh2STQ6DF2SjxACPT09Ay6BP3bsGHJycsI7JRYvXoyioiLpO0Fd17Ft2za88MILePLJJ1FdXS3978nhGLpkD0IInDt3bsAl8G1tbSguLh5wCXxWVpY0oXXq1Cncd999mDlzJtavX4+srCyzS6KxY+iSfYUugQ+dpmtqakJfX99ll8AnJyebXeoAuq5j69atePHFF7FhwwZ897vfleYLBcXE0CVn8fl84UvgGxsbw5fAV1RUhIO4uLjYtG1rra2tuPfee1FaWor169cjMzPTlDpo3DB0ydlCl8CHZsONjY1oaWlBUVFROIQrKysxadKkce02dV3Hli1b8NJLL2HDhg244YYb2N3aE0OXaDBd19Ha2jrgEniPx4M5c+Zcdgl8Ipw8eRL33nsv5s2bh3Xr1rG7tTeGLtFIBAKByy6BV1U1fJquqqoKpaWlcV0Cr2katmzZgq1bt+KZZ57B9ddfz+7W/hi6RKMReQl8KIibm5uRl5cXDuHFixejoKBgyCBtaWnBfffdhwULFqC2thYZGRkm/C7IBAxdokQRQuDMmTMDLoE/e/Zs+BL4qqoqLFq0CH/+85/xpz/9CZs2bcJ1113H7tZZGLpE40nTNBw7diy8f/gf//gHlixZgq1btyI9Pd3s8sh4DF0iIwkh2Nk6W9S/fN6tRzQOGLgUDUOXiMhADF0iIgMxdImIDMTQJSIyEEOXiMhADF0iIgMxdImIDMTQJSIyEEOXiMhADF0iIgMxdImIDJQU4+08QE5ElEDsdImIDMTQJSIyEEOXiMhADF0iIgMxdImIDMTQJSIy0P8Bc3LgDlWBk1kAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "%matplotlib inline\n",
    "\n",
    "n_instances = 10\n",
    "class_1 = np.random.rand(n_instances//2, 3)/5\n",
    "class_2 = (0.6, 0.1, 0.05) + np.random.rand(n_instances//2, 3)/5\n",
    "data = np.concatenate((class_1, class_2))\n",
    "colors = [\"red\"] * (n_instances//2) + [\"green\"] * (n_instances//2)\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111, projection='3d', xticks=[], yticks=[], zticks=[])\n",
    "ax.scatter(data[:, 0], data[:, 1], data[:, 2], c=colors);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The high-dimensional space is endowed with some measure of distance, the Euclidean distance being the simplest case. We can calculate all pairwise distances between the data points:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:21.407379Z",
     "start_time": "2018-11-19T20:10:21.393951Z"
    }
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "w = np.zeros((n_instances, n_instances))\n",
    "for i, j in itertools.product(*[range(n_instances)]*2):\n",
    "    w[i, j] = np.linalg.norm(data[i]-data[j])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This matrix is sometimes called the Gram or the kernel matrix. The Gram matrix contains a fair bit of information about the topology of the points in the high-dimensional space, but it is not easy to see. We can think of the Gram matrix as the weighted adjacency matrix of a graph: two nodes represent two data instances. Their distance as contained in the Gram matrix is the weight on the edge that connects them. If the distance is zero, they are not connected by an edge. In general, this is a dense graph with many edges -- sparsity can be improved by a distance function that gets exponentially smaller.\n",
    "\n",
    "What can we do with this graph to find the clusters? We could look for the max-cut, that is, the collection of edges that would split the graph in exactly two if removed, while maximizing the total weight of these edges [[1](#1)]. This is a well-known NP-hard problem, but it also very naturally maps to an Ising model.\n",
    "\n",
    "The spin variables $\\sigma_i \\in \\{-1, +1\\}$ take on value $\\sigma_i = +1$ if a data instance is in cluster 1 (nodes $V_1$ in the graph), and $\\sigma_i = -1$ if the data instance is in cluster 2 (nodes $V_2$ in the graph). The cost of a cut is\n",
    "\n",
    "$$\n",
    "\\sum_{i\\in V_1, j\\in V_2} w_{ij}\n",
    "$$\n",
    "\n",
    "Let us assume a fully connected graph. Then, accounting for the symmetry of the adjacency matrix, we can expand this as\n",
    "$$\n",
    "\\frac{1}{4}\\sum_{i, j} w_{ij} - \\frac{1}{4} \\sum_{i, j} w_{ij} \\sigma_i \\sigma_j\n",
    "$$\n",
    "$$\n",
    "= \\frac{1}{4}\\sum_{i, j\\in V} w_{ij} (1- \\sigma_i \\sigma_j).\n",
    "$$                 \n",
    "\n",
    "By taking the negative of this, we can directly solve the problem by a quantum optimizer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the Max-Cut problem by QAOA\n",
    "\n",
    "Most quantum computing frameworks have convenience functions defined for common graph optimization algorithms, and max-cut is a staple. This reduces our task to importing the relevant functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:23.147272Z",
     "start_time": "2018-11-19T20:10:21.412811Z"
    }
   },
   "outputs": [],
   "source": [
    "from qiskit import Aer\n",
    "from qiskit.aqua import QuantumInstance\n",
    "from qiskit.aqua.algorithms import QAOA\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.aqua.translators.ising import max_cut"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setting $p=1$ in the QAOA algorithm, we can initialize it with the max-cut problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:10:28.190764Z",
     "start_time": "2018-11-19T20:10:23.152849Z"
    }
   },
   "outputs": [],
   "source": [
    "qubit_operators, offset = max_cut.get_max_cut_qubitops(w)\n",
    "p = 1\n",
    "optimizer = COBYLA()\n",
    "qaoa = QAOA(qubit_operators, optimizer, p, operator_mode='matrix')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here the choice of the classical optimizer `COBYLA` was arbitrary. Let us run this and analyze the solution. This can take a while on a classical simulator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:12:33.139743Z",
     "start_time": "2018-11-19T20:10:28.202147Z"
    }
   },
   "outputs": [],
   "source": [
    "backend = Aer.get_backend('statevector_simulator')\n",
    "quantum_instance = QuantumInstance(backend, shots=100)\n",
    "result = qaoa.run(quantum_instance)\n",
    "x = max_cut.sample_most_likely(result['eigvecs'][0])\n",
    "graph_solution = max_cut.get_graph_solution(x)\n",
    "print('energy:', result['energy'])\n",
    "print('max-cut objective:', result['energy'] + offset)\n",
    "print('solution:', max_cut.get_graph_solution(x))\n",
    "print('solution objective:', max_cut.max_cut_value(x, w))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the solution, the cut matches the clustering structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the Max-Cut problem by annealing\n",
    "\n",
    "Naturally, the same problem can be solved on an annealer. Our only task is to translate the couplings and the on-site fields to match the programming interface:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-11-19T20:12:37.587621Z",
     "start_time": "2018-11-19T20:12:36.386739Z"
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import dimod\n",
    "\n",
    "J, h = {}, {}\n",
    "for i in range(n_instances):\n",
    "    h[i] = 0\n",
    "    for j in range(i+1, n_instances):\n",
    "        J[(i, j)] = w[i, j]\n",
    "\n",
    "model = dimod.BinaryQuadraticModel(h, J, 0.0, dimod.SPIN)\n",
    "sampler = dimod.SimulatedAnnealingSampler()\n",
    "response = sampler.sample(model, num_reads=10)\n",
    "print(\"Energy of samples:\")\n",
    "for solution in response.data():\n",
    "    print(\"Energy:\", solution.energy, \"Sample:\", solution.sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you look at the first sample, you will see that the first five data instances belong to the same graph partition, matching the actual cluster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
    "[1] Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. Schuyler, Hong, S., Karalekas, P., Osborn, C. B., Papageorge, A., Peterson, E. C., Prawiroatmodjo, G., Rubin, N., Ryan, Colm A., Scarabelli, D., Scheer, M., Sete, E. A., Sivarajah, P., Smith, Robert S., Staley, A., Tezak, N., Zeng, W. J., Hudson, A., Johnson, Blake R., Reagor, M., Silva, M. P. da, Rigetti, C. (2017). [Unsupervised Machine Learning on a Hybrid Quantum Computer](https://arxiv.org/abs/1712.05771). *arXiv:1712.05771*. <a id='1'></a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
